import java.util.List;

/**
 * 移出链表元素
 */

public class LeetCode203 {

    /**
     * 双指针  移出链表的元素，   p1 和 p2 指针 分别指向 头 和 首元素， 遍历找到对应值Node，将p1.next指向 p2.的next 这样 p2就被移除掉了。
     * 这里为什么不用p2.prv = p2.next 因为这是单向链表 不是双链表没有prv指针。
     *
     * @param head
     * @param val
     */
    void removeElement(ListNode head, int val) {
        ListNode s = new ListNode(-1, head);
        ListNode p1 = s;
        ListNode p2 = s.next;
        while (p2 != null) {
            if (p2.val == val) {
                p1.next = p2.next;
            } else {
                p1 = p1.next;
                p2 = p2.next;
            }
        }

    }


    /**
     * 递归  移出链表的元素，
     */
    public ListNode removeElement2(ListNode node, int val) {
        //链表结束返回null
        if (node == null) {
            return null;
        }
        //当相等，就跳过当前指针
        if (node.val == val) {
            return removeElement2(node.next, val);
        } else {
            node.next = removeElement2(node.next, val);
            return node;
        }
    }


    /**
     * 按下表删除元素
     */
    public int recursion(ListNode p, int n) {
        if (p == null) {
            return 0;
        }
        int nth = recursion(p.next, n);
        if (p.val == n) {
            p.next = p.next.next;
        }
        return nth + 1;

    }

    /**
     * 调用recursion 通过下标删除元素
     */
    public ListNode removeUseRecursion(ListNode head, int n) {
        //使用哨兵  解决 头尾问题
        ListNode s = new ListNode(-1, head);
         recursion(s, n);
        return head;
    }




    class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }

        @Override
        public String toString() {
            return "ListNode{" +
                    "val=" + val +
                    ", next=" + next +
                    '}';
        }
    }
}
